﻿//kotori和⽓球（组合数学）
//https://ac.nowcoder.com/acm/problem/50039

//#include<iostream>
//using namespace std;
//
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//
//    int ret = n;
//    while (--m)
//    {
//        ret *= (n - 1);
//        ret %= 109;
//    }
//    cout << ret;
//}


//⾛迷宫（BFS）
//https://www.nowcoder.com/practice/e88b41dc6e764b2893bc4221777ffe64?tpId=308&tqId=40477&ru=/exam/oj

//#include <iostream>
//#include <cstring>
//#include <queue>
//using namespace std;
//
//const int N = 1005;
//char map[N][N];
//int dist[N][N];
//int n, m, x1, y1, x2, y2;
//int dx[4] = { 0,0,-1,1 };
//int dy[4] = { -1,1,0,0 };
//queue<pair<int, int>>q;
//
//int bfs()
//{
//    memset(dist, -1, sizeof(dist));
//    q.push({ x1,y1 });
//    dist[x1][y1] = 0;
//    while (!q.empty())
//    {
//        auto [x, y] = q.front();
//        q.pop();
//        for (int i = 0; i < 4; i++)
//        {
//            int a = x + dx[i], b = y + dy[i];
//            if (a >= 1 && a <= n && b >= 1 && b <= m && map[a][b] != '*' && dist[a][b] == -1)
//            {
//                dist[a][b] = dist[x][y] + 1;
//                q.push({ a,b });
//                if (a == x2 && b == y2)
//                    return dist[a][b];
//            }
//        }
//    }
//    return -1;
//}
//
//int main() {
//    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            cin >> map[i][j];
//        }
//    }
//
//    cout << bfs();
//}



